'''
An implementation of Chord.
Chord is distributed hash table. Check:
http://pdos.csail.mit.edu/chord/
And for the paper check:
http://pdos.csail.mit.edu/chord/papers/paper-ton.pdf

Unlike the usual Chord implements, this one is implemented using TCP
XMLRPC protocol.

@author: Hatem Oraby
'''
from sys import maxint

from twisted.web import xmlrpc, server
import xmlrpclib
from twisted.internet import reactor
Proxy = xmlrpc.Proxy
from copy import copy


waitValue = "wait"
noAnswer = "noAnswer"
m = 10

class _Request():
    def __init__(self):        
        self._requests = {}
        self._requestIdCounter = 0
    
    def newRequest(self, method, *args, **keyargs):
        '''The method returns request id for future reference'''
        id = self._requestIdCounter
        #Yea, requests can be overridden by new requests, check later
        self._requestIdCounter = (self._requestIdCounter + 1)%maxint
        self._requests[id] = (method, args, keyargs)
        return id
    
    def getRequest(self, id):
        '''The method returns the request but deletes it from it's
        memory, it should be called pop request'''
        req = self._requests[id]
        del self._requests[id]
        return req
    
class ChordPeer():
    def __init__(self, id, address):
        self.id = id
        self.address = address

class Chord(xmlrpc.XMLRPC):
    #Should i leave them static like this?
    stablizePeriod = 10
    fixFingerPeriod = 5
    succListPeriod = 5
    succListLen = 10
    predecessorPeriod = 20
    
    def __init__(self,m , address, nDash, bootStrap = False):
        xmlrpc.XMLRPC.__init__(self)
        #id is derived from hashing address
        #Chord attributes
        self.m = m
        self._id = hash(address)%(2**m)
        print "My Address: " + str(address)
        print "My id: " + str(self._id)
        
        #self._successor = ChordPeer(successorID,successorAddress)
        self._successor = None
        #self._successor = ChordPeer(nDash.id,nDash.address) 
        #Okay , just assume for now that nDash is our successor until
        # we get our real successor.
        self._predecessor = None
        self._predecessorCallId = None #Will hold the ID returned by callLater 
                                       # for _predecessorExpire
        
        #Finger Table
        self._fingerTableStart = [] #of size m
        self._fingerTable = [] #of size m
        for i in range(m):
            fingerValue = (self._id + (2**i))%(2**m)
            self._fingerTableStart.append(fingerValue)
            print "i: " + str(i) + "\t FingerStart: " + str(fingerValue)
            self._fingerTable.append(None)
        self._fingerIndex = 0 #up to mod(m)
        self._isStablized = False
        
        #None Chord attributes
        self._address = address #The xmlRPC address of the current machine
        self._request = _Request()
        #TODO: The id should be derived from the address??
    
        #TODO: Maintain a successors list
        self._succList = [] #of size Chord.succListLen
        for i in range(Chord.succListLen):
            self._succList.append(None)
        self._succIndex = 0
        
        #self.initFIngerTable(nDash)
        self.debug()
        if bootStrap:
            self._joinBootStrap()
        else:
            self._join(nDash.id, nDash.address)
    
    def xmlrpc_findSuccessor(self, id, requestingAddress, requestID):
        def foundPredecessor(predecessorId, predecessorAddress):
            def gotSuccessor(resultList):
                #print "Result 2: " + str(resultList)
                successorId,successorAddress = resultList
                proxy = Proxy(requestingAddress)
                proxy.callRemote("gotFindSuccessor", successorId,
                                 successorAddress,requestID)
            nDash = ChordPeer(predecessorId, predecessorAddress)
            proxy = Proxy(nDash.address)
            defer = proxy.callRemote("getSuccessor")
            defer.addCallbacks(gotSuccessor, gotError)
        
        def gotError(error):
            print "1.Some error happened"
            print "Error: " + str(error)
            print "Requesting Address: " + str(requestingAddress)
            print "Request ID: " + str(requestID)
            proxy = Proxy(requestingAddress)
            proxy.callRemote("gotFindSuccessor", error, requestID)
                
        reqId = self._request.newRequest(foundPredecessor)
        self.xmlrpc_findPredecessor(id, self._address, reqId)
        return waitValue #Just tell him to waits, if we returned nothing
                         #(i.e None returned) then XML-RPC library will
                         #complain about None value returned.
            
    def xmlrpc_gotFindSuccessor(self, id, address, requestId):
        #Okay, I finally got an answer
        if type(id) != int:
            #I may have got error
            print "Got Error or something else: " + str(id)
        else:
            method,args,keyArgs = self._request.getRequest(requestId)
            method(id,address,*args,**keyArgs)
        return noAnswer
    
    def xmlrpc_findPredecessor(self, id, requestingAddress, requestId):
        #The following 2 commented lines are pseudo code which is 
        # implemented in the rest of this method.
        ##while not nDash <= id < nDash.successor:
        ##    nDash = nDash.xmlrpc_closestPrecedingFinger(id)
        ##return nDash
        def checkCondition(resultList):
            peerId,peerAddress = resultList
            nDash = ChordPeer(peerId,peerAddress)
            proxy = Proxy(nDash.address)
            defer = proxy.callRemote("getSuccessor")
            #print "Got Successor: " + str(gotSuccessor)
            #print "Got Error: " + str(gotError)
            defer.addCallbacks(gotSuccessor,gotError,[nDash])
            
        def gotSuccessor(resultList, nDash):
            #print "Result List: " +str(resultList)
            successorId,successorAddress = resultList
            #We got nDash successor , now lets ask him for the closestPrcedingFinger(id)
            nDash.successor = ChordPeer(successorId,successorAddress)
            #if not nDash.id <= id < nDash.successor:
            if not self.isInBetween(nDash.id, nDash.successor.id, id, False, True):    
                #I need to call nDash.closesestPrecesdingFinger(id) , but i need to get
                # nDash successor first
                proxy = Proxy(nDash.successor.address)
                defer = proxy.callRemote("closestPrecedingFinger", id)
                defer.addCallbacks(checkCondition,gotError)
            else:
                #I got the solution
                proxy = Proxy(requestingAddress)
                proxy.callRemote("gotFindPredecessor",nDash.id,nDash.address,requestId)
        
        def gotError(error):
            print "2.Got Error: " + str(error)
            print "Should pass  error to the requesting address."
            print "Id: " + str(id) + "\tRequesting Address: " + str(requestingAddress)
            print
        
        checkCondition([self._id, self._address])
        return waitValue
    #End of method
        
    def xmlrpc_getSuccessor(self):
        if self._successor ==  None:
            return -1,-1
        else:
            return self._successor.id, self._successor.address
    
    def xmlrpc_gotFindPredecessor(self, id, address, requestId):
        if type(requestId) != int:
            print "Something unknown happened"
        else:
            method,args,keyargs = self._request.getRequest(requestId)
            method(id,address, *args, **keyargs)
        return noAnswer    
        
    
    def xmlrpc_closestPrecedingFinger(self, id):
        iterate = range(self.m)
        list.reverse(iterate)
        if not self._isStablized:
            if self.isInBetween(self._id, id, self._successor.id, 
                                    False, False):#Maybe i have it
                return self._id,self._address
            else:#I don't have it but my finger table ain't good, so just
                 # pass the next guy
                return self._successor.id, self._successor.address
        else:
            for i in iterate:
                #if self._id <= self._fingerTable[i].id <= id:
                if self.isInBetween(self._id, id, self._fingerTable[i].id, 
                                    False, False):
                    return self._fingerTable[i].id, self._fingerTable[i].address
            
        #Maybe there is something wrong with the finger table,
        # just return the successor
        return [self._id, self._address]
        

    #initialize finger table of local node (self)
    #nDash is an arbitrary node already in the network
    def initFIngerTable(self, nDash):
        def nextFinger(id, address,i):
            #Can this cause error??
            self._fingerTable[i] = ChordPeer(id, address)
            i += 1 #Or should i pass the i as well??
            if i < m:
                reqId = self._request.newRequest(nextFinger, i)
                proxy.callRemote("findSuccessor", self._fingerTableStart[i],
                                 self._address,reqId)
            else:
                #Now we finished initializing all the fingers, we can start
                # now on periodically fixing them/
                self._isStablized = True
                self.xmlrpc_fixFingers()
        
        def gotFirstFinger(id, address):
            #Set the successor and now we can start to stablize
            self._successor = self._fingerTable[0] = ChordPeer(id,address)
            self.xmlrpc_stablize()
            
            #self._predecessor = successor.predecessor
            def gotPredecessor(resultList):
                successorPredecessorId, successorPredecessorAddress = resultList
                if successorPredecessorId != -1:
                    self._predecessor = ChordPeer(successorPredecessorId,
                                                  successorPredecessorAddress)
            proxy = Proxy(self._successor.address)
            defer = proxy.callRemote("getPredecessor")
            defer.addCallbacks(gotPredecessor, gotError)
            
            #successor.predecessor = self #Which is equal to successor.notify(self)
            proxy = Proxy(self._successor.address)
            proxy.callRemote("notify", self._id, self._address)
            
            i = 1
            if i < self.m:
                proxy = Proxy(nDash.address)
                reqId = self._request.newRequest(nextFinger,i)
                proxy.callRemote("findSuccessor", self._fingerTableStart[i],
                                 self._address,reqId)
        
        def gotError(error):
            print "3.Got Error: " + str(error)
            print "Should pass to the requesting address the error"
        
        #nDash = self._successor
        proxy = Proxy(nDash.address)
        reqId = self._request.newRequest(gotFirstFinger)
        
        print "i: " + str(0)
        print "FInger Table: " + str(self._fingerTableStart[0])
        print "Address: " + self._address
        print "RequestId : " + str(reqId)
        proxy.callRemote("findSuccessor",self._fingerTableStart[0], self._address,reqId)
        #defer.callbacks(nextFinger,gotError) 
        #It doesn't matter really, the RPC reply would be to wait
    
    #Update all nodes whose finger tables should refer to n (i.e. me):
    def updateOthers(self):
        #for i in range(m):
        #    #find last node p whose i(th) finger might be n
        #    p = find_predecessor(n - (2**(i-2)))
        #    p.updateFingerTable(self,i)
        def gotPredecessor(PredecessorId, PredecessorAddress, **keyDict):
            i = keyDict['i']
            proxy = Proxy(PredecessorAddress)
            proxy.callRemote("updateFingerTable", self._id, i, self._address)
            
        for i in range(m):
            reqId = self._request.newRequest(gotPredecessor, **{"i":i})
            id = (self._id - (2**i))%(2**m) #Should i add the %m???
            self.xmlrpc_findPredecessor(id, self._address, reqId)
    
    def xmlrpc_updateFingerTable(self, s, i, sAddress):
        #if self._id < s <= self._fingerTable[i].id:
        if self.isInBetween(self._id, self._fingerTable[i], s, True, False):
            #I Should check for node existence
            finger[i].id = s
            finger[i].address = sAddress
            
            #predecessor.updateFingerTable(s,i)
            if self._predecessor != None:
                proxy = Proxy(self._predecessor.address)
                proxy.callRemote("updateFingerTable", s, i, sAddress)
    
    def xmlrpc_getPredecessor(self):
            if self._predecessor == None:
                return -1,-1
            else:
                #I want to know here if he is alive before replying?
                return self._predecessor.id, self._predecessor.address
    
    def isInBetween(self, first, last, suspect, includeFirst = True,
                    includeLast = True):
        if first >= last:
            last = (last + (2**self.m))
            if suspect <= first:
                suspect = (suspect + (2**self.m))
        
        if includeFirst:
            if includeLast:
                return first <= suspect <= last
            else:
                return first <= suspect < last
        else:
            if includeLast:
                return first < suspect <= last
            else:
                return first < suspect < last
        
    def _join(self, nDashId, nDashAddress):
        #Only address is needed
        nDash = ChordPeer(nDashId, nDashAddress)
        self._predecessor = None
        
        def foundSuccessor(successorId, successorAddress):
            if successorId == -1: #I'm the bootstrap node??
                successorId = self._id
                successorAddress = self._address

            self._successor = ChordPeer(successorId, successorAddress)
            self._succList[0] = copy(self._successor)
            proxy = Proxy(self._successor.address)
            proxy.callRemote("notify", self._id, self._address)
            
            self.xmlrpc_stablize()
            self.xmlrpc_fixFingers()
            self.stablizeSucc()
                
        reqId = self._request.newRequest(foundSuccessor)
        proxy = Proxy(nDash.address)
        proxy.callRemote("findSuccessor", self._id, self._address,reqId)
        return noAnswer
        
    
    def _joinBootStrap(self):
        self._successor = ChordPeer(self._id, self._address)
        #Set finger table, successors list, predecessor to me
        for i in range(m):
            self._fingerTable[i] = copy(self._successor)
        for i in range(self.succListLen):
            self._succList[i] = copy(self._successor)
        self._predecessor = copy(self._successor)
 
        self.xmlrpc_stablize()
        self.xmlrpc_fixFingers()
        self.stablizeSucc()
            
    def xmlrpc_stablize(self):
        if hasattr(reactor, "_id"):
            self.reflectName()
        def gotPredecessor(resultList):
            def successorAlive(dummyResult):
                '''The successors predecessors is alive and he is my new
                successor'''
                self._successor = ChordPeer(successorPredecessorId, 
                                            successorPredecessorAddress)
                self._succList[0] = copy(self._successor)
                #And as a shortcut, correct all the finger in between
                for i in range(m):
                    if self.isInBetween(self._id, self._successor.id, 
                                       self._fingerTableStart[i], False, True):
                        self._fingerTable[i] = copy(self._successor)
                    else:
                        #Just save us time
                        self._fingerIndex = i
                        break

            def successorDead(error):
                '''The successors predecessors is dead'''
                #Just wait till the successor realize that his current 
                #predecessor is dead then contact the successor again.
                
            successorPredecessorId, successorPredecessorAddress = resultList
            if successorPredecessorId != -1 and \
                successorPredecessorAddress != self._address and\
                self.isInBetween(self._id, self._successor.id, 
                                 successorPredecessorId, False, False):
                #The successor i've asked said that there is someone in the 
                #middle, however that guy maybe dead but the successor didn't
                #realize that yet, if i connected to the dead guy i will fail
                #so i have first to make sure that he is alive before declaring
                #him my successor. 
                poteinalSucc = ChordPeer(successorPredecessorId, 
                                         successorPredecessorAddress)
                #Just make sure that he is alive by asking him about
                #his successor.
                proxy = Proxy(poteinalSucc.address, self._id, self._address)
                defer = proxy.callRemote("notify", self._id, self._address)
                defer.addCallbacks(successorAlive, successorDead)
            else:
                proxy = Proxy(self._successor.address)
                proxy.callRemote("notify", self._id, self._address)
        
        def gotError(error):
            print "4.Something bad happened"
            print "Error: " + str(error)
            #So i probably lost the successors, get the closest
            #alive successor from the successors list.
            for i in range(1,Chord.succListLen):
                if self._succList[i] != None:
                    self._successor = copy(self._succList[i])
                    #self._succList[0] = copy(self._succList[i])
                    for j in range(Chord.succListLen-i):
                        #Shit may happen here, we should do this in a
                        #kind of critical section to avoid racing with
                        #successors list stablize.
                        self._succList[j] = copy(self._succList[i+j])
                    for k in range(j+1,Chord.succListLen):
                        self._succList[k] = None
                    self._succIndex = 0
                    self.xmlrpc_stablize() 
                    break
            else:
                print "I've lost connection with all alive"
                   
        proxy = Proxy(self._successor.address)
    
        defer = proxy.callRemote("getPredecessor")
        defer.addCallbacks(gotPredecessor, gotError)
        #I should manage call later so that only one stablize is called
        # and the others are canceled. 
        reactor.callLater(Chord.stablizePeriod, self.xmlrpc_stablize) 
        return noAnswer
    
    def xmlrpc_notify(self, claimedPredecessorId, claimedPredecessorAddress):
        if hasattr(reactor, "_id"):
            self.reflectName()
        if self._predecessor == None or \
            self.isInBetween(self._predecessor.id, self._id, claimedPredecessorId, 
                             False, False):
            self._predecessor = ChordPeer(claimedPredecessorId, claimedPredecessorAddress)
            if self._predecessorCallId != None:
                self._predecessorCallId.cancel()
                self._predecessorCallId = None
            self._predecessorCallId = reactor.callLater(Chord.predecessorPeriod,
                                                        self._predecessorExpire)
        return noAnswer
    
    def _predecessorExpire(self):
        self._predecessor = None
        self._predecessorCallId = None
        #print "Predecessor Expired"
    
    def stablizeSucc(self):
        '''Stablizes successors list '''
        if hasattr(reactor, "_id"):
            self.reflectName()
        def gotSuccessor(successorInfo, successorIndex = None):
            #successorIndex is equal to None so i can pass it as
            #a keyword along with xmlrpc data. It should never be 
            #none.
            successorId, successorAddress = successorInfo
            #Ok, no goddamn questions about security, let's implement the thing
            #first right then question the security and extreme scenarios later.
            self._succList[successorIndex+1] = ChordPeer(successorId, successorAddress)
            
            self._succIndex = (self._succIndex+1)%(Chord.succListLen - 1)
            reactor.callLater(Chord.succListPeriod, self.stablizeSucc)
            #print "SuccessorIndex =  " + str(self._succIndex) 
    
        def gotError(error,successorIndex = None):
            print "5.Something wrong happened."
            print "The guy's index is:" + str(successorIndex)
            print "Error Type: "  + str(type(error))
            print "Error: "  + str(type(error))
            if successorIndex != 0: 
                #If it's our immediate successor then wait do nothing and wait 
                #for stablize() to fix it. If it's not then ask the guy before
                #it about his successor.
                self._succIndex -= 1
            reactor.callLater(Chord.succListPeriod, self.stablizeSucc)

        #proxy = Proxy(self._successor.address)
        nextSuccessor = self._succList[self._succIndex]
        if nextSuccessor == None: #Entry hasn't been initialized yet
            '''If an entry hasn't been initialized yet then we should ask
            the guy before him again, if the guy we are asking is our next
            immediate successor and he is none then we would search the 
            successors list ascendingly and the first non "None" entry 
            we be our immediate successor, if all the successors list 
            are none then me and the chord ring are screwed.'''
            if self._succIndex == 0:#Can this really happen???
                for i in range(1,Chord.succListLen):
                    if self._succList[i] != None:
                        nextSuccessor = self._succList[i]
                        break  
                if nextSuccessor == None:
                    #We are screwed, we lost all connections to successors
                    #maybe we can connect to the closest alive fingers and 
                    #ask him about his predecessor and ask the predecessor  
                    #about his predecessor and so on until we find someone 
                    #without a predecessor then that would be our successor, 
                    print "I'm an orphan now and don't know what to do"
                    return #or should stop the reactor,maybe someone will
                           #connect on me??
            else:
                #Something might be wrong here
                nextSuccessor = self._succList[self._succIndex-1]
        proxy = Proxy(nextSuccessor.address)
        defer = proxy.callRemote("getSuccessor")
        defer.addCallbacks(gotSuccessor, gotError, 
                           callbackKeywords = {"successorIndex":self._succIndex},
                           errbackKeywords = {"successorIndex":self._succIndex})
    
    def xmlrpc_fixFingers(self):
        if hasattr(reactor, "_id"):
            self.reflectName()
        def gotResult(fingerId,fingerAddress, **keyargs):
            if fingerId == None or fingerId == -1:
                #Do nothing , i'm asking a guy who's not yet stablized.
                return        
            index = keyargs['i'] 
            self._fingerTable[index] = ChordPeer(fingerId, fingerAddress)
            self._isStablized = True
            for entry in self._fingerTable:
                if entry == None:
                    self._isStablized = False
                    return

        reqId = self._request.newRequest(gotResult, **{"i":self._fingerIndex})
        self.xmlrpc_findSuccessor(self._fingerTableStart[self._fingerIndex], self._address, reqId)
        self._fingerIndex = (self._fingerIndex+1)%m
        reactor.callLater(Chord.fixFingerPeriod, self.xmlrpc_fixFingers)
        
    
    def debug(self):
        print
        if self._predecessor == None:
            print "Predecessor: " + str(None),
        else:
            print "Predecessor: " + str(self._predecessor.id),    
        print "\tId: " + str(self._id),
        if self._successor == None:
            print "\tSuccessor: " + str(None)
        else:
            print "\tSuccessor: " + str(self._successor.id)
        
        print "FingerTable: " + str(self._request._requestIdCounter)
        for i in range(m):
            print "FingerStart: " + str(self._fingerTableStart[i]),
            try:
                print "\tFingerValue: " + str(self._fingerTable[i].id)
            except:
                print "\tFIngerValue: " + str(self._fingerTable[i])
        
        print "Successors List: "
        for i in range(Chord.succListLen):
            print "Successor " + str(i)+ ": ",
            try:
                print str(self._succList[i].id)
            except:
                print str(self._succList[i])
        if hasattr(reactor, "_id"): 
            if not self._address.endswith(reactor._id):
                print "I'm quitting"
                import os
                os._exit(1)
            else:
                print "I've passed the test"
        else:
            print "I got a virgin unmanipulated reactor"
            print "My Port: " + str(sys.argv[1])
        reactor.callLater(15,self.debug)    
    
    def reflectName(self):
#        print "My port is: " + self._address.split(":")[-1]
#        print "My reactorId: " + reactor._id
        pass
    
def startListening():
    port = sys.argv[1]
    if not str.isdigit(port):
        print "Wrong usage."
        print "Port must be a valid port number"
    else:
        port = int(port)
        #Check for validity of range of the port

    import socket
    myIP = socket.gethostbyname(socket.gethostname())
    print "My IP: " + myIP + "\t and my Port: " + str(port)

    address = "http://"+myIP+":"+str(port)
    print "My address is: " + address
    
    if len(sys.argv) < 3: #I should create a network
        nDash = ChordPeer(hash(address)%(2**m), address)
        chord = Chord(10, address, nDash, bootStrap = True)
    else:
        nDash = ChordPeer(hash(address)%(2**m), sys.argv[2])
        chord = Chord(10, address, nDash)
        
    reactor.listenTCP(port, server.Site(chord))

if __name__ == '__main__':
    import sys
    if len(sys.argv) < 2:
        print "Wrong Usage."
        print "Usage: " + sys.argv[0] + " PortNumber"  
        sys.exit()
    
    reactor.callLater(0,startListening)
    reactor.run()
    
    